8.3 找出雙連通元件

圖 G 上面的雙連通元件 (Biconnected Component) 是指，一個極大的子圖，使得該子圖內不存在關節點。
經過一些有趣的證明以後，可以知道圖 G 上的每一條邊，至多屬於一個雙連通元件。
但是，同一個點可能分屬多個雙連通元件。因此，如果要找出雙連通元件，得把邊分成很多等價類來下手。

由於每一個點可能屬於許多雙連通元件，我們可以用一個點來代表雙連通元件、而將雙連通元件與接觸到的割點以邊連起來。連起來以後可以證明它會形成一棵樹，而這樣的樹我們稱為 BC樹 (Block-Cut Tree)。

要怎麼找出雙連通元件呢？一個可行的演算法如下：首先找一棵生成樹，接著，對於每一條不是樹上的邊 (u, v)，都可以在樹上找一條路徑，形成一個環，這個環通常稱為 fundamental cycle。簡單來說，這個環上所有的邊，都屬於同一個雙連通元件。因此，我們可以用併查集(或甚至是全部記錄下來以後跑一次 DFS) 把雙連通元件裡面的邊都合併起來，就能得到要得結果啦。

8.4 耳分解 Ear Decomposition

還有另外一種建構雙連通圖的方式：從一個圈開始，然後每一次挑兩個點，額外增加一條路徑。如果這兩個點允許是同一個點，那麼這個耳分解生出來的圖是 2-邊連通的(即拿掉一條邊，圖仍然是連通的，但可能拿掉點就會不連通了)。如果每次挑選的兩個點都是相異的點，那這個耳分解又被稱為開耳分解 (open ear decomposition)。